#pragma once

#include <vector>

class Solution {
public:
    int findDuplicate(const std::vector<int>& nums) {
        int n = nums.size() - 1;
        std::vector table(n, 0);
        for (auto num : nums) {
            if (table.at(num - 1))
                return num;
            table.at(num - 1) = 1;
        }
        return -1;
    }
};
